package 力扣_高阶数据结构.优先级队列;

import java.util.*;

/**
 * @author zx
 * @create 2022-08-15 20:42
 */
public class 最小K个数 {
    public int[] smallestK(int[] arr, int k) {
        //最小的k个数,取小用大
        if(arr.length == 0 || k == 0){
            return new int[0];
        }
        int[] res = new int[k];
        //构造一个最大堆,JDK默认是最小堆,使用比较器改造为最大堆(最大堆：堆顶元素是最大的)
        //要把最小堆改为最大堆,就是告诉编译器值越大,让编译器看来它反而小
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2 - o1;
            }
        });
        for(int i = 0;i < arr.length;i++){
            if(queue.size() < k){
                queue.offer(arr[i]);
            }else{
                //当前判断扫描元素和堆顶元素的关系
                //若扫描元素 > 堆顶元素 > 堆中的所有值,这个值一定不是要找的数
                int peek = queue.peek();
                if(arr[i] > peek){
                    continue;
                }else{
                    //此时当前元素 < 堆顶元素,将堆顶元素出队,将较小值i入队
                    queue.poll();
                    queue.offer(arr[i]);
                }
            }
        }
        //此时最大堆中就保存了最小的k个数
        for(int j = 0;j < k;j++){
            res[j] = queue.poll();
        }
        return res;
    }
}
